package gold.enterprise;

import javafx.util.Pair;

public class MicroSoftFour {

    class ListNode {
        public int val;
        ListNode child;
        ListNode next;
        ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode getPlainList(ListNode head) {
        return getPlainListByRecursive(head).getKey();
    }

    public Pair<ListNode, ListNode> getPlainListByRecursive(ListNode head) {
        if (null == head) return null;

        ListNode cur = head;    // cur遍历list
        while (null != cur.next) {
            if (null != cur.child) {
                //找到一个有child的
                ListNode curNextPart = cur.next;
                Pair<ListNode, ListNode> nextLayerPart = getPlainListByRecursive(cur.child);

                cur.next = nextLayerPart.getKey();
                nextLayerPart.getKey().prev = cur;

                nextLayerPart.getValue().next = curNextPart;//接尾部
                curNextPart.prev = nextLayerPart.getValue();
            }

            cur = cur.next;
        }

        // cur现在已经是尾元素了
        return new Pair<>(head, cur);
    }


    public static void main(String[] args) {
        MicroSoftFour solution = new MicroSoftFour();
    }

}
